package com.om39a.ds;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author om39a
 * 
 */
public class MergSort {

	public static void main(String[] args) {
		Integer[] val = { 6, 4, 3, 2, 7, 9, 5, 1, 0, 8 };
		List<Integer> toSort = Arrays.asList(val);
		MergSort mergSort = new MergSort();
		System.out.println(mergSort.mergSort(toSort));
	}

	private List<Integer> mergSort(List<Integer> toSort) {
		if (toSort.size() <= 1) {
			return toSort;
		} else {
			int mid = toSort.size() / 2;
			List<Integer> leftSubList = mergSort(toSort.subList(0, mid));
			List<Integer> rightSubList = mergSort(toSort.subList(mid,
					toSort.size()));
			return merg(leftSubList, rightSubList);
		}
	}

	private List<Integer> merg(List<Integer> leftToSort,
			List<Integer> rightToSort) {
		List<Integer> mergerlist = new ArrayList<Integer>();
		int leftIndex = 0, rightIndex = 0;
		while (true) {
			if (leftIndex >= leftToSort.size()) {
				mergerlist.addAll(rightToSort.subList(rightIndex,
						rightToSort.size()));
				return mergerlist;
			} else if (rightIndex >= rightToSort.size()) {
				mergerlist.addAll(leftToSort.subList(leftIndex,
						leftToSort.size()));
				return mergerlist;
			} else if (leftToSort.get(leftIndex) < rightToSort.get(rightIndex)) {
				mergerlist.add(leftToSort.get(leftIndex));
				leftIndex++;
			} else {
				mergerlist.add(rightToSort.get(rightIndex));
				rightIndex++;
			}
		}
	}
}
